﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Media;

namespace Assignment3
{
    public class MazeGenerator
    {
        //WallBlocks will be place at positions whose value is true
        private bool[,] maze;

        public bool[,] Maze
        {
            get { return maze; }
        }

        //number of row and columm in maze. They should be odd numbers.
        private int row;
        private int columm;

        public int Row
        {
            get { return row; }
        }

        public int Columm
        {
            get { return columm; }
        }

        private Random random = new Random();
        int randomNumber;

        /// <summary>
        /// Create a 25x25 maze
        /// </summary>
        public MazeGenerator()
            : this(25, 25)
        {
        }

        /// <summary>
        /// Create a square maze with give value. 
        /// </summary>
        /// <param name="matrixSize">Matrix size should be odd number for best result</param>
        public MazeGenerator(int matrixSize)
            : this(matrixSize, matrixSize)
        {
        }

        /// <summary>
        /// Create a custom maze with give value. 
        /// </summary>
        /// <param name="matrixWidth">Number of columms of the maze. It should be odd number</param>
        /// <param name="matrixHeight">Number of rows of the maze. It should be odd number</param>
        public MazeGenerator(int matrixWidth, int matrixHeight)
        {
            row = matrixHeight;
            columm = matrixWidth;
            maze = new bool[row, columm];
            generateMaze();
        }

        /// <summary>
        /// Generate value for random maze
        /// </summary>
        public void generateMaze()
        {
            //initialize the blank map
            for (int i = 0; i < row; i++)
                for (int j = 0; j < columm; j++)
                    maze[i, j] = true;

            //stack hold a list of cell location
            Stack<int[]> cellStack = new Stack<int[]>();

            //number of cells in grid
            int totalCells = (row / 2) * (columm / 2);

            //the init cell which store the coordinate of the cell
            int[] currentCell = { 1, 1 };
            maze[currentCell[0], currentCell[1]] = false;

            //number of cells visited
            int visitedCells = 1;

            while (visitedCells < totalCells)
            {
                //Find all neighbors of CurrentCell with all walls intact
                List<int[]> neighborCells = new List<int[]>();
                if (currentCell[1] - 2 > 0 && maze[currentCell[0], currentCell[1] - 3] && maze[currentCell[0], currentCell[1] - 1] && maze[currentCell[0] - 1, currentCell[1] - 2] && maze[currentCell[0] + 1, currentCell[1] - 2])
                    neighborCells.Add(new int[] { currentCell[0], currentCell[1] - 2 });

                if (currentCell[0] + 2 < columm && maze[currentCell[0] + 2, currentCell[1] - 1] && maze[currentCell[0] + 3, currentCell[1]] && maze[currentCell[0] + 2, currentCell[1] + 1] && maze[currentCell[0] + 1, currentCell[1]])
                    neighborCells.Add(new int[] { currentCell[0] + 2, currentCell[1] });

                if (currentCell[1] + 2 < columm && maze[currentCell[0], currentCell[1] + 1] && maze[currentCell[0] + 1, currentCell[1] + 2] && maze[currentCell[0], currentCell[1] + 3] && maze[currentCell[0] - 1, currentCell[1] + 2])
                    neighborCells.Add(new int[] { currentCell[0], currentCell[1] + 2 });

                if (currentCell[0] - 2 > 0 && maze[currentCell[0] - 2, currentCell[1] - 1] && maze[currentCell[0] - 1, currentCell[1]] && maze[currentCell[0] - 2, currentCell[1] + 1] && maze[currentCell[0] - 3, currentCell[1]])
                    neighborCells.Add(new int[] { currentCell[0] - 2, currentCell[1] });

                //if one or more found 
                if (neighborCells.Count > 0)
                {
                    //Choose one at random
                    randomNumber = random.Next(neighborCells.Count);
                    int[] tmpCell = neighborCells.ElementAt(randomNumber);
                    maze[tmpCell[0], tmpCell[1]] = false;
                    //knock down the wall between it and CurrentCell
                    maze[(currentCell[0] + tmpCell[0]) / 2, (currentCell[1] + tmpCell[1]) / 2] = false;
                    //push CurrentCell location on the CellStack
                    cellStack.Push(currentCell);
                    //make the new cell CurrentCell
                    currentCell = tmpCell;
                    //add 1 to VisitedCells
                    visitedCells++;
                }
                else
                {
                    //pop the most recent cell entry off the CellStack and make it CurrentCell
                    currentCell = cellStack.Pop();
                }
            }
        }

    }
}
